一、學習目標

在演算法題目中，很多時候會遇到計算某個區間的總和，例如：

• 求第L到第R個數字的總和。
• 計算滿足條件的子陣列數量。
• 判斷是否有子陣列和可被整除。

如果用最直覺的暴力法，每次查詢都需要 O(n) 時間，但當查詢次數很多時會超時。
解決方法就是前綴和 (Prefix Sum)，只要一次預處理，就能做到每次查詢 O(1)。

二、前綴和概念

定義

給定陣列 nums，定義前綴和陣列 prefix：
prefix[i] = nums[0] + nums[1] + ... + nums[i]

利用前綴和，我們可以在 O(1) 的時間計算任意區間 [L, R] 的總和：
sum(L, R) = prefix[R] - prefix[L - 1]

前綴和範例

假設陣列：

nums = [2, 4, 5, 7]
prefix = [2, 6, 11, 18]

若要求區間 [1,3] (即 nums[1]+nums[2]+nums[3])：

sum(1,3) = prefix[3] - prefix[0] = 18 - 2 = 16

一次計算完成，效率比暴力法快非常多。

暴力法 vs 前綴和

三、CSES實戰演練

題目1:Static Range Sum Queries

原題:
https://cses.fi/problemset/task/1646
題意:
給定一個長度為 n 的陣列，處理 q 次查詢，每次查詢輸出區間 [a, b] 的總和。

解題思路:
預先計算前綴和。
對於每次查詢 [a, b]，輸出：

prefix[b]−prefix[a−1]

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> nums(n + 1, 0), prefix(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        prefix[i] = prefix[i - 1] + nums[i];
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << prefix[b] - prefix[a - 1] << "\n";
    }
    return 0;
}

題目2:Subarray Divisibility

原題:
https://cses.fi/problemset/task/1662

題意:
給定一個長度為 n 的陣列，求出有多少個子陣列的總和能被 n 整除。

解題思路:

• 計算前綴和 prefix[i]。
• 對於每個 prefix[i]，計算 prefix[i] % n。
• 如果兩個不同索引有相同的餘數，則它們之間的子陣列總和能被 n 整除。
• 使用 unordered_map 統計每個餘數出現的次數，套用組合公式：

cnt = Σ C(k, 2)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    long long ans = 0, sum = 0;
    unordered_map<int, long long> mp;
    mp[0] = 1; // 初始條件

    for (int i = 0; i < n; i++) {
        sum += nums[i];
        int mod = ((sum % n) + n) % n; // 避免負數
        ans += mp[mod];
        mp[mod]++;
    }

    cout << ans << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1: Range Sum Query - Immutable

原題:
https://leetcode.com/problems/range-sum-query-immutable/description/

題意:
實作一個類別 NumArray，支援以下操作：
初始化：輸入整數陣列。
查詢：回傳區間 [i, j] 的總和。

class NumArray {
public:
    vector<int> prefix;  // 前綴和陣列

    // 初始化前綴和
    NumArray(vector<int>& nums) {
        int n = nums.size();
        prefix.resize(n + 1, 0);  // 多開一格，prefix[0] = 0

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    // 查詢區間 [left, right] 的總和
    int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
};

複雜度分析:

題目2: Subarray Sum Equals K

原題:
https://leetcode.com/problems/subarray-sum-equals-k/description/

題意:
給定一個整數陣列 nums 和一個整數 k，請計算總共有多少個子陣列的總和等於 k。

解題思路

• 用變數 sum 計算當前前綴和。
• 利用 unordered_map 紀錄「某個前綴和出現的次數」。
• 若 sum - k 曾出現過，代表存在一段子陣列和為 k。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int sum = 0, ans = 0;

        for (int x : nums) {
            sum += x;
            if (mp.count(sum - k))
                ans += mp[sum - k];
            mp[sum]++;
        }

        return ans;
    }
};

複雜度分析: